/*
 * BitLinked.h
 *
 *  Created on: 27/08/2012
 *      Author: marciocs5
 */

#ifndef BITLINKED_H_
#define BITLINKED_H_

#include "BitTools.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
/*
 *	Estrutura de dados que é um vetor de bits encadeado(???).
 *
 *	A estrutura representa um conjunto. Os elementos são armazenados
 *	em no vetor vector como um vetor caracteristico.
 *
 *	ant e prox indicam respectivamente a ultima palavra não-nula e a primeira
 *	não-nula posterior a cada palavra. Ou seja, se ant[i] = j então vector[j] !=
 *	0 e vector[j+1]= vector[j+2] = ... = vector[i-1] = 0 e analogamente para
 *	prox.
 *
 * */
template<typename T>
class BitVectorFix {
private:
	T* vector;// vetor de bits
	T* subvector;
	long vectorsz;// tamanho do vetor
	long subvectorsz;
	long logw;// log do tamanho da palavra
	long sizew;// tamanho da palavra
	long mask;
	long n;// numero de bits

protected:
	// determina dentro da palavra qual o deslocamento para o bit i
	long inWordIdx(long i);

	// determina a palavra em que o bit i esta
	long wordIdx(long i);

	// determina dentro da palavra idx, o proximo bit 1 depois de i
	long leastBit(long i, long idx);

	long leastBitSub(long i, long idx);

	//conta no numero de bits 1 na palavra idx
	long countBit(long idx);

	long countBitSub(long idx);

public:
	//construtor
	BitVectorFix(long n);

	//destrutor
	virtual ~BitVectorFix();

	//numero de bits
	virtual long size();

	//tamanho do vetor de bits
	virtual long sizeInWord();

	//coloca um bit no conjunto
	virtual void toSet(long i);

	//retira um bit do conjunto
	virtual void toCompl(long i);

	//coloca todos os bits no conjunto
	virtual void allToSet();

	//retira todos os vertices do conjunto
	virtual void allToCompl();

	//verifica se um vertice esta no conjunto
	virtual bool isInSet(long i);

	//OU
	virtual void logicor(BitVectorFix<T>* v);

	//E
	virtual void logicand(BitVectorFix<T>* v);

	//NÃO
	virtual void logicneg();

	//numero de bits setados no conjunto
	virtual long cardOfset();

	//verifica se o conjunto é vazio
	virtual bool isEmpty();

	//next bit no conjuto segundo sua ordem natural
	virtual long nextSet(long i);

	//for debug
	virtual void show();
};

template<typename T>
BitVectorFix<T>::BitVectorFix(long n){
	this->n = n;
	logw = inline_ceillog(sizeof(T), 1) + 3;
	sizew = sizeof(T)*8;
	mask = (1LL << logw) - 1;
	vectorsz = (n >> logw) + 1;
	subvectorsz = (vectorsz >> logw) +1;
	vector = new T[vectorsz];
	subvector = new T[subvectorsz];
	for(long i = 0; i < vectorsz; i++){
		vector[i] = 0;
	}
	for(long i = 0; i < subvectorsz; i++){
		subvector[i] = 0;
	}
}

template<typename T>
BitVectorFix<T>::~BitVectorFix(){
	delete vector;
	delete subvector;
}

template<typename T>
inline long BitVectorFix<T>::inWordIdx(long i){
	return i & mask;
}

template<typename T>
inline long BitVectorFix<T>::wordIdx(long i){
	return i >> logw;
}

template<>
inline long BitVectorFix<int>::leastBit(long idx, long i){
	return builtinLeast<int>(vector[idx] & posmasksimp[i]);
}

template<>
inline long BitVectorFix<long>::leastBit(long idx, long i){
	return builtinLeast<long>(vector[idx] & posmasklsimp[i]);
}

template<>
inline long BitVectorFix<int>::leastBitSub(long idx, long i){
	return builtinLeast<int>(subvector[idx] & posmasksimp[i]);
}

template<>
inline long BitVectorFix<long>::leastBitSub(long idx, long i){
	return builtinLeast<long>(subvector[idx] & posmasklsimp[i]);
}

template<typename T>
inline long BitVectorFix<T>::countBit(long idx){
	return builtinCounter<T>(vector[idx]);
}

template<typename T>
inline long BitVectorFix<T>::countBitSub(long idx){
	return builtinCounter<T>(subvector[idx]);
}

template<typename T>
inline long BitVectorFix<T>::size(){
	return n;
}

template<typename T>
inline long BitVectorFix<T>::sizeInWord(){
	return vectorsz;
}

template<typename T>
inline void BitVectorFix<T>::toSet(long i){
	long index = wordIdx(i);
	vector[index] |= (1LL << (inWordIdx(i)));
	subvector[wordIdx(index)] |= (1LL << (inWordIdx(index)));
}

template<typename T>
inline void BitVectorFix<T>::toCompl(long i){
	long index = wordIdx(i);
	vector[index] &= ~(1LL << (inWordIdx(i)));
	if(vector[index] == 0) subvector[wordIdx(index)] &= ~(1LL << (inWordIdx(index)));
}

template<typename T>
inline void BitVectorFix<T>::allToSet(){
	memset(vector, 255, vectorsz*sizeof(T));
	memset(subvector, 255, subvectorsz*sizeof(T));
}

template<typename T>
inline void BitVectorFix<T>::allToCompl(){
	memset(vector, 255, vectorsz*sizeof(T));
	memset(subvector, 255, subvectorsz*sizeof(T));
}

template<typename T>
inline bool BitVectorFix<T>::isInSet(long i){
	return (vector[wordIdx(i)] & (1LL << (inWordIdx(i)))) != 0;
}

template<typename T>
inline void BitVectorFix<T>::logicor(BitVectorFix<T>* v){
	T* a = vector;
	T* b = v->vector;
	long offset = 0;
	long offsetsub = 0;
	T* suba = subvector;
	T* subb = v->subvector;
	long look;

	for(long i = 0; i < subvectorsz; i++){
		suba[i] |= subb[i];
		look = leastBitSub(i, 0);
		offset = (i<< logw);
		while(look != -1){
			a[offset+look] |= b[offset+look];
			look++;
			if(look >= sizew) look= -1;
			else look = leastBitSub(i, look);
		}
	}
}

template<typename T>
inline void BitVectorFix<T>::logicand(BitVectorFix<T>* v){
	T* a = vector;
	T* b = v->vector;
	long offset = 0;
	T* suba = subvector;
	T* subb = v->subvector;
	long look;

	for(long i = 0; i < subvectorsz; i++){
		suba[i] &= subb[i];
		look = leastBitSub(i, 0);
		offset = (i << logw);
		while(look != -1){
			a[offset + look] &= b[offset + look];
			if(a[offset + look] == 0) subvector[wordIdx(offset+ look)] &= ~(1LL << (inWordIdx(offset+ look)));
			look++;
			if(look >= sizew) look= -1;
			else look = leastBitSub(i, look);;
		}
	}
}

template<typename T>
inline void BitVectorFix<T>::logicneg(){
	T* a = vector;
	long i = 0;
	T* c = a + vectorsz;
	for(; a < c; a++, i++){
		*a = ~(*a);
		if(*a == 0) subvector[wordIdx(i)] &= ~(1LL << (inWordIdx(i)));
		else subvector[wordIdx(i)] |= (1LL << (inWordIdx(i)));
	}
}

template<typename T>
inline long BitVectorFix<T>::cardOfset(){
	T* a = vector;
	long offset = 0;
	long offsetsub = 0;
	T* suba = vector;
	long look;
	long count = 0;

	for(long i = 0; i < subvectorsz; i++){
		look = leastBitSub(i, 0);
		offset = (i << logw);
		while(look != -1){
			count += countBit(offset + look);
			look++;
			if(look >= sizew)look = -1;
			else look = leastBitSub(i, look);
		}
	}

	return count;
}

template<typename T>
inline bool BitVectorFix<T>::isEmpty(){
	T* a = subvector;
	T* c = a + subvectorsz;
	for(; a < c; a++){
		if((*a) != 0) return false;
	}
	return true;
}

template<>
inline long BitVectorFix<int>::nextSet(long i){
	long finder = builtinLeast<long>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
	if(finder >= 0)return finder + wordIdx(i) << logw;
	for(long j = wordIdx(i)+1; j < vectorsz ; j++){
		if((subvector[wordIdx(j)] & (1LL << (inWordIdx(j)))) != 0){
			finder = leastBit(j << logw, 0) + j << logw;
			return finder;
		}
	}
	return -1;
}

template<>
inline long BitVectorFix<long>::nextSet(long i){
	long finder = builtinLeast<long>(vector[wordIdx(i)] & posmasksimp[inWordIdx(i)]);
	if(finder >= 0)return finder + wordIdx(i) << logw;
	for(long j = wordIdx(i)+1; j < vectorsz ; j++){
		if((subvector[wordIdx(j)] & (1LL << (inWordIdx(j)))) != 0){
			finder = leastBit(j << logw, 0) + j << logw;
			return finder;
		}
	}
	return -1;
}

template<typename T>
inline void BitVectorFix<T>::show(){
	printf("\n Estrutura!\n");
	printf("vetor de base! \n");
	for(long i = 0; i < size(); i++){
		if(isInSet(i))printf("<%lu>", i);
	}
	printf("\n");
}

#endif /* BITLINKED_H_ */
